#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 // Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
 
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL) {
            return head;
        }
        if (head->next == NULL) {
            return head;
        }
        ListNode* sort_H = insertionSortList(head->next);
        
        ListNode* curr = sort_H;
        ListNode* pre = head;
        bool Z = false;
        while (curr && head->val > curr->val) {
            Z = true;
            pre = curr;
            curr = curr->next;
        }
        if (Z) {
            ListNode* temp = pre->next;
            pre->next = head;
            pre->next->next = temp;
        }
        else {
            head->next = curr;
        }

        return (Z ? sort_H : head);
        



    }
};

//int main() {
//    ListNode* head = new ListNode(4);
//    ListNode* p1 = new ListNode(2);
//    ListNode* p2 = new ListNode(1);
//    ListNode* p3 = new ListNode(3);
//    head->next = p1;
//    p1->next = p2;
//    p2->next = p3;
//    Solution S;
//    ListNode* T = S.insertionSortList(head);
//    return 0;
//}